/*
 * Ken Anderson, 2009
 */

#include "Graph.h"
#include "util.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>


struct Loc { int x; int y; };
struct Room { 
  Node * node;
  bool connected;
};



Node::Node(int id, float x, float y)
{
	mXLoc = x;
	mYLoc = y;
	mID = id;
}

Node::~Node()
{
}

void Node::AddEdge(Edge edge) 
{
	mOutEdges.push_back(edge);
	if(TRACE) printf("Added edge %i from node %i to node %i\n",edge.GetID(), mID, edge.ToNode()->GetID());
}

Edge::Edge( int id, Node * from, Node * to, float w )
{
	mID = id;
	mFromNode = from;
	mToNode = to;
	mWeight = w;
}

Graph::Graph()
{
	srand(RANDOM_SEED);
	mNodeIdCount = 0;
	mEdgeIdCount = 0;
}

Graph::~Graph()
{
}
	
// Cannot return reference to node because underlying datastructure may change.
// So we return the ID instead.
int Graph::AddNode(float x, float y)
{
	Node node( mNodeIdCount++, x, y );
	mNodes.push_back( node );
	if(TRACE) printf("Added Node %i\n", node.GetID() );
	return node.GetID();
}

int Graph::AddEdge( Node * from, Node * to, float weight )
{
	Edge edge( mEdgeIdCount++, from, to, weight);
	from->AddEdge(edge);	//copy
	return edge.GetID();
}

void Graph::print(FILE * stream)
{
	if(TRACE) fprintf(stream, "Nodelist[%d] -- node(x,y): toNode(weight) toNode(weight) ...\n", (int)mNodes.size());
	for(unsigned int i=0; i<mNodes.size(); i++)
	{
		Node node = mNodes[i];
		if(TRACE) fprintf(stream, "  %i(%f,%f)[%u]: ", node.GetID(), node.GetX(), node.GetY(), node.NumOutEdges() );
		for(unsigned int j=0; j<node.NumOutEdges(); j++)
		{
			Edge * edge = node.GetOutEdge(j);
			if(TRACE) fprintf(stream, "%i(%f) ", edge->ToNode()->GetID(), edge->GetWeight() );
		}
		if(TRACE) fprintf(stream, "\n");
	}
}

Node* Graph::GetNode( float x, float y )
{
	unsigned int numNodes = GetNumOfNodes();
	for( unsigned int i=0; i<numNodes; i++)
	{
		Node * node = GetNode(i);
		if( aboutEqualTo( node->GetX(), x ) && aboutEqualTo( node->GetY(), y ) )
			return node;
	}
	return NULL;
}

Edge* Graph::GetEdge( Node* from, Node* to ) 
{
	// error case
	if( !from || !to )
		return NULL;
	
	// Search for the edge
	for( unsigned int i=0; i<from->NumOutEdges(); i++)
	{
		Edge * edge = from->GetOutEdge(i);
		if( to == edge->ToNode() )
			return edge;
	}
	return NULL;
}

Map::Map(const char* filename) : Graph()
{
	
	FILE * file;
	int width=0;
	int height=0;
	char buffer[100];
	char * wallMap = NULL;
  int result=0;
	
	file = fopen( filename, "r" );
	if( !file )
	{
		if(FATAL) printf("Could not find file %s \n", filename);
		exit(1);
	}

	while( fscanf( file, "%s", buffer )!=EOF )
	{
		if( strcmp(buffer, "type")==0 )	{ // currently ignore
			result = fscanf( file, "%s", buffer );
			//printf("%s\n", buffer);
		}
		else if( strcmp(buffer, "width")==0 ) {
			result = fscanf( file, "%d", &width );
      if( result != 1 )
      {
        if(TRACE) printf("Failed to read width");
      }
      else
      {
        if(TRACE) printf("%s %d\n", buffer, width);
      }
		}
		else if( strcmp(buffer, "height")==0 ) {
			result = fscanf( file, "%d", &height );
      if( result != 1 )
      {
        if(TRACE) printf("Failed to read height");
      }
      else
      {
        if(TRACE) printf("%s %d\n", buffer, height);
      }
		}
		else if( strcmp(buffer, "map")==0 )
		{
			if(TRACE) printf("%s\n", buffer);
			wallMap = new char[width*height+1];
			for( int i=0; i<width*height; i++)
			{
				wallMap[i]=' ';
				while( wallMap[i]=='\n' || wallMap[i]==' ' )	// skip white space
				{
					result = fscanf( file, "%c", &(wallMap[i]) );
					if( result != 1 )
					{
						if(TRACE) printf("Reached end of map too soon.  Check width, height, and map characters.\n");
						exit(1);
					}
				}
			}
			wallMap[width*height]='\0';
			if(TRACE) printf("%s %s\n", buffer, wallMap);
		}
	}

	fclose( file );

	Init(width,height,wallMap);
	if( wallMap )
		delete[] wallMap;
}

Map::Map(unsigned int width, unsigned int height, const char* wallMap) : Graph()
{
	Init( width, height, wallMap );
}

void Map::Init(unsigned int width, unsigned int height, const char* wallMap)
{
	mWidth = width;
	mHeight = height;

	// Temporary array to store the location of the node within the vector
	unsigned int * nodeIndex = NULL;
	nodeIndex = new unsigned int [height*width+2];
	
	// error check 
	if( nodeIndex == NULL )
		exit(0);

	//Make nodes
	for( unsigned int y=0; y<height; y++) {
		for( unsigned int x=0; x<width; x++ ) {
			if( wallMap[y*width+x] != '@' )	{ // character denotes a wall
				nodeIndex[y*width+x] = AddNode( (float)x, (float)y );
			}
			else {
				nodeIndex[y*width+x] = 99999;
			}
		}
	}
	
	// Make edges (must only do after nodes are finished)
	unsigned int fromIndex;
	unsigned int toIndex;
	Node* fromNode;
	Node* toNode;
	for( unsigned int y=0; y<height; y++) {
		for( unsigned int x=0; x<width; x++ ) {
			fromIndex = y*width+x;
			if( nodeIndex[fromIndex] != 99999 ) {
				fromNode = GetNode( nodeIndex[fromIndex] );

				// Left
				if( x >= 1 ) {
					toIndex = y*width+(x-1);
					if( nodeIndex[toIndex] != 99999 ) {
						toNode=GetNode( nodeIndex[toIndex] );
						if( toNode != NULL ) {
							AddEdge( fromNode, toNode, 1.0f );
						}
					}
				}
				
				// Right
				if( x+2 <= width ) {
					toIndex = y*width+(x+1);
					if( nodeIndex[toIndex] != 99999 ) {
						toNode=GetNode( nodeIndex[toIndex] );
						if( toNode != NULL ) {
						AddEdge( fromNode, toNode, 1.0f );
						}
					}
				}
				//Above
				if( y >= 1 ) {
					toIndex = (y-1)*width+x;
					if( nodeIndex[toIndex] != 99999 ) {
						toNode=GetNode( nodeIndex[toIndex] );
						if( toNode != NULL ) {
							AddEdge( fromNode, toNode, 1.0f );
						}
					}
				}
				// Below
				if( y+2 <= mHeight ) {
					toIndex = (y+1)*width+x;
					if( nodeIndex[toIndex] != 99999 ) {
						toNode=GetNode( nodeIndex[toIndex] );
						if( toNode != NULL ) {
							AddEdge( fromNode, toNode, 1.0f );
						}
					}
				}
			}
		}
	}

	delete [] nodeIndex;
}

Map::~Map()
{
}

void Map::CreateMap( 
			   char* filename, int key, 
			   const int roomHeight, const int roomWidth, 
			   const int horizontalNumRooms, const int verticalNumRooms, 
			   const int doorwayWidth )
{
	int connectedCountDown = horizontalNumRooms * verticalNumRooms;

	// Create graph of rooms
	Graph roomGraph;
	for( int y=0; y<verticalNumRooms; y++ )
		for( int x=0; x<horizontalNumRooms; x++ )
			roomGraph.AddNode( (float)x, (float)y );

	// Create index array for fast access when creating edges.
	Room ** roomIndexTable;
	roomIndexTable=new Room*[verticalNumRooms]; //creates a new array of pointers to int objects
	for(int i=0; i<verticalNumRooms; ++i)
		roomIndexTable[i]=new Room[horizontalNumRooms];
	Node * node;
	Loc loc;
	for( unsigned int i=0; i<roomGraph.GetNumOfNodes(); i++ ) {
		node = roomGraph.GetNode(i);
		loc.x = (unsigned int)node->GetX();
		loc.y = (unsigned int)node->GetY();
		roomIndexTable[ loc.y ][ loc.x ] .node = node;
		roomIndexTable[ loc.y ][ loc.x ] .connected = false;
	}

	// OpenList of all nodes that are on edge of connected graph
	std::vector<Loc> openList;
	
	// Choose random starting room
	srand(key);
	loc.x = rand()%verticalNumRooms;
	loc.y = rand()%horizontalNumRooms;
	openList.push_back(loc);
	roomIndexTable[loc.y][loc.x].connected = true;
	connectedCountDown--;

	// Connect all nodes.  This technique may cause duplicates on the open list.
	Room * room;
	Room * room2;
	while( connectedCountDown != 0 )
	{
		// Error check
		if( openList.size() == 0 ) {
			printf("Error, the open list is zero");		
			exit(0);
		}

		// Choose random node
		int index = rand()%openList.size();
		loc = openList[index];
		openList.erase(openList.begin()+index);	//A little slow
		room = &roomIndexTable[loc.y][loc.x];

		// Add all edges
		if( loc.y > 0 ) {
			loc.y--;
			room2 = &roomIndexTable[loc.y][loc.x];
			if( ! (room2->connected) ) {
				roomGraph.AddEdge( room->node, room2->node, 1.0 );
				room2->connected = true;
				connectedCountDown--;
				openList.push_back(loc);
			}
			loc.y++;
		}
		if( loc.x > 0 ) {
			loc.x--;
			room2 = &roomIndexTable[loc.y][loc.x];
			if( ! (room2->connected) ) {
				roomGraph.AddEdge( room->node, room2->node, 1.0 );
				room2->connected = true;
				connectedCountDown--;
				openList.push_back(loc);
			}
			loc.x++;
		}
		if( loc.y < verticalNumRooms-1 ) {
			loc.y++;
			room2 = &roomIndexTable[loc.y][loc.x];
			if( ! (room2->connected) ) {
				roomGraph.AddEdge( room->node, room2->node, 1.0 );
				room2->connected = true;
				connectedCountDown--;
				openList.push_back(loc);
			}
			loc.y--;
		}
		if( loc.x < horizontalNumRooms-1 ) {
			loc.x++;
			room2 = &roomIndexTable[loc.y][loc.x];
			if( ! (room2->connected) ) {
				roomGraph.AddEdge( room->node, room2->node, 1.0 );
				room2->connected = true;
				connectedCountDown--;
				openList.push_back(loc);
			}
			loc.x--;
		}
	}

	// Create actual graph
	char * graph = new char[verticalNumRooms*roomHeight*horizontalNumRooms*roomWidth];
	for( int roomY=0; roomY<verticalNumRooms; roomY++ ) {
		for( int roomX=0; roomX<horizontalNumRooms; roomX++ ) {
			for( int y=0; y<roomHeight; y++ ) {
				for( int x=0; x<roomWidth; x++ ) {
					if( y==0 || x==0 ) {
						graph[ (roomY*roomHeight+y)*(verticalNumRooms*roomHeight)+(roomX*roomWidth+x) ] = '@';
					} else {
						graph[ (roomY*roomHeight+y)*(verticalNumRooms*roomHeight)+(roomX*roomWidth+x) ] = '.';
					}
				}
			}
		}
	}
	// Make the connections between rooms
	Edge * edge;
	for( unsigned int index=0; index<roomGraph.GetNumOfNodes(); index++ ) {
		node = roomGraph.GetNode(index);
		for( unsigned int edgeIndex=0; edgeIndex < node->NumOutEdges(); edgeIndex++ ) {
			edge = node->GetOutEdge(edgeIndex);
			int roomY = (int)std::max( edge->ToNode()->GetY(), edge->FromNode()->GetY() );
			int roomX = (int)std::max( edge->ToNode()->GetX(), edge->FromNode()->GetX() );
			if( aboutEqualTo( edge->ToNode()->GetX(), edge->FromNode()->GetX() ) ) {// horizontal edge
				int positionOnWall = rand()%(roomWidth-doorwayWidth)+1;
				for( int doorIndex=positionOnWall; doorIndex<positionOnWall+doorwayWidth; doorIndex++) {
					graph[ (roomY*roomHeight+0)*(verticalNumRooms*roomHeight)+(roomX*roomWidth+doorIndex) ] = '.';
				}
			}
			if( aboutEqualTo( edge->ToNode()->GetY(), edge->FromNode()->GetY() ) ) { // vertical edge
				int positionOnWall = rand()%(roomHeight-doorwayWidth)+1;
				for( int doorIndex=positionOnWall; doorIndex<positionOnWall+doorwayWidth; doorIndex++) {
					graph[ (roomY*roomHeight+doorIndex)*(verticalNumRooms*roomHeight)+(roomX*roomWidth+0) ] = '.';
				}
			}
		}
	}

	// Print
	FILE * file = fopen(filename, "w");
	fprintf(file, "type quad\n");
	fprintf(file, "height %i\n", verticalNumRooms*roomHeight);
	fprintf(file, "width %i\n", horizontalNumRooms*roomWidth);
	fprintf(file, "map\n");
	for( int row=0; row<horizontalNumRooms*roomWidth; row++ ) {
		for( int col=0; col<verticalNumRooms*roomHeight; col++ ) {
			fprintf(file, "%c", graph[row*verticalNumRooms*roomHeight+col]);
		}
		fprintf(file, "\n");
	}
	fflush(file);
	fclose(file);

	delete [] graph;
}
